package utils;
import java.util.*;

public class SkipList {
    class SkipNode {
        int key;
        int val;
        int level;
        ArrayList<SkipNode> nexts;

        public SkipNode(){}

        public SkipNode(int key, int val){
            this.key = key;
            this.val = val;
        }

        public SkipNode(int level, int key, int val){
            this.key = key;
            this.val = val;
            this.nexts = new ArrayList<>(level);
        }
    }

    int maxLevel;
    int num;
    SkipNode head;

    //需要设定跳表所能允许的最大层数
    public SkipList(int maxLevel) {
        SkipNode head = new SkipNode(maxLevel, Integer.MIN_VALUE, 0);
        this.head = head;
        this.maxLevel = maxLevel;
        this.num = 0; //头结点不计入节点总数
    }

    //============================================================================

    public boolean isEmpty() {
        return head == null || num == 0;
    }

    //查询对应key的节点对应的val
    //没有查找到按照返回特定的负值表示【我们强制要求key全部为正数】
    public int find(int key) {
        if (isEmpty()) return -2; //-2表示跳表未初始化
        return find(key, head, head.level);
    }

    public int find(int key, SkipNode cur, int level) {
        while (level >= 0) {
             cur = findNextNode(key, cur, level);
             level--;
        }
        if (cur.key != key) return -1; //只能得到目标key的前面最大的那个结点，因此说明目标key对应的结点不存在，返回-1
        return cur.val;
    }

    //寻找到**等于key或者小于key最大的那个结点**
    public SkipNode findNextNode(int key, SkipNode cur, int level) {
        SkipNode next = cur.nexts.get(level);
        while (next.key <= key) {
            cur = next;
            next = cur.nexts.get(level);
        }
        return cur;
    }


    //======================================================================================

    //随机返回一个介于1 ~ maxLevel - 1的随机层数，用于创建新节点
    public int randomLevel() {
        int level = 0;
        // < 0.5的概率正好是1/2，每次符合一次前面的条件，概率就会在上一层通过概率的基础上乘以1/2【随机事件的乘法法则】
        // 任何节点的层数都不可以到达最大层数
        while (Math.random() < 0.5 && level < this.maxLevel - 1) {
            level++;
        }
        return level;
    }

    //是否存在key对应的节点
    public boolean contains(int key) {
        return find(key) > 0;
    }

    public boolean add(int key, int val) {

        if (isEmpty() || contains(key)) return false;

        int randomLevel = randomLevel();
        SkipNode newNode = new SkipNode(key, val, randomLevel);

        SkipNode cur = head;
        while (randomLevel >= 0) {
            cur = findNextNode(key, cur, randomLevel);
            SkipNode next = cur.nexts.get(randomLevel);

            //newNode这一层的后继设为cur的后继
            newNode.nexts.add(randomLevel, next);
            //cur这一层的后继设置为newNode
            cur.nexts.set(randomLevel, newNode);

            //层数减一
            randomLevel--;
        }
        this.num++;
        return true;
    }

    // ========================================================

    //重写一个查找前面一个节点的方法
     //寻找到**小于key最大的那个结点**
     public SkipNode findPreNode(int key, SkipNode cur, int level) {
        SkipNode next = cur.nexts.get(level);
        while (next.key < key) {
            cur = next;
            next = cur.nexts.get(level);
        }
        return cur;
    }

    //删除节点
    public boolean remove(int key) {
        if (isEmpty()) return false;

        boolean isRemoved = false;
        SkipNode cur = head;
        int level = cur.level;
        while (level >= 0) {
            cur = findPreNode(key, cur, level);
            level = cur.level;

            //将要删除的节点的next赋值给pre
            SkipNode rNode = cur.nexts.get(level), next = rNode.nexts.get(level);
            cur.nexts.set(level, next);

            level--;

            //将标志位设置为true
            isRemoved = true;
        }
        if (isRemoved) this.num--;
        return isRemoved;
    }
    
}
